package LeetCode.interview;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.prism.impl.Disposer.Target;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.launcher.resources.launcher;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;
import 算法.排序.归并排序.MergeSortTest1;
import 算法.排序.快速排序.QuickSort;

/*
 * 
原题　
	Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


题目大意
	求出最接近target的sum；
解题思路
	和 3Sum解题报告 很像，与之不同的是，不再是求三个数的和是不是为0，而是看三个数的和与target的差是否为最小，只需记录当前最优解并不断更新其值就可。
 * @Date 2017-10-05 22：53
 */
public class _016_3Sum_Closest {
	public int threeSumClosest(int[] num, int target) {  
		if (num==null || num.length<3)	return 0;
		
		int len = num.length;
		int i, l, r;
		int closestDist = Integer.MAX_VALUE;
		int closestSum = 0;
		//排序下
		Arrays.sort(num);
		/*
		 * 三分法
		 */
		for (i = 0; i < len-2; i ++) {
			l = i+1;
			r = len-1;
			while (l < r) {
				int curSum = num[i] + num[l] + num[r];
				if (curSum > target) {
					if (curSum-target < closestDist) {
						closestDist = curSum-target;
						closestSum = curSum;
					}
					r--;
				} else if (target > curSum) {
					if (target-curSum < closestDist) {
						closestDist = target-curSum;
						closestSum = curSum;
					}
					l++;
				} else {
					//相等 target == sum
					return curSum;
				}
			}
		}
		return closestSum;
    }

    
    public static void main(String[] args) {
		_016_3Sum_Closest obj = new _016_3Sum_Closest();

		LogUtils.println("结果", obj.threeSumClosest(new int[]{0, 0, 0}, 1));
	}

}
